import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Leetcode139 {
    HashMap<String, Boolean> map= new HashMap<String, Boolean>();
    public boolean wordBreak(String s, List<String> wordDict) {
        for (String s1 : wordDict) {
            map.put(s1,true);
        }
        boolean[] dp = new boolean[s.length() + 1];
        dp[0]=true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = i-1; j >=0 ; j--) {
                dp[i]=dp[j]&&checkWord(s.substring(j,i));
                if (dp[i]) break;
            }
        }
        return dp[s.length()];

    }
    public boolean checkWord(String s){
        return map.getOrDefault(s,false);
    }

    public static void main(String[] args) {

    }
}
